/*
 * Alloy Analyzer
 * Copyright (c) 2002 Massachusetts Institute of Technology
 *
 * The Alloy Analyzer is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * The Alloy Analyzer is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with the Alloy Analyzer; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

package alloy.symm;

import java.util.Iterator;
import java.util.Map;

import alloy.ast.ASTDepthFirstVisitor;
import alloy.ast.HasType;
import alloy.ast.Leaf;
import alloy.ast.LeafExpr;
import alloy.ast.LeafId;
import alloy.ast.Location;
import alloy.ast.Node;

/**
 * Finds nodes that are constrained according to a given pattern.
 * Used to detect special cases for symmetry breaking.
 */
class PatternMatch_V extends ASTDepthFirstVisitor {
    /**
     * Tests whether two AST subtrees are identical except for
     * a renaming of identifiers.  If they are, returns a
     * {@link Map} relating the corresponding {@link LeafId}s.
     * If they are node, returns <code>null</code>.
     */
    static Map subtreesAreIdentical(Node n1_, Node n2_, Map correspLeafIds_) {
	if (!n1_.getClass().equals(n2_.getClass())) return null;
	if (!(n1_.numChildren() == n2_.numChildren())) return null;
	if (n1_ instanceof HasType &&
	    !((HasType)n1_).getType().equals(((HasType)n2_).getType()))
	    return null;

	if (n1_ instanceof Leaf) {
	    LeafId leafId1 = ((Leaf)n1_).getLeafId();
	    LeafId leafId2 = ((Leaf)n2_).getLeafId();
	    LeafId correspLeafId = (LeafId)correspLeafIds_.get(leafId1);
	    if (correspLeafId!=null && !correspLeafId.equals(leafId2))
		return null;
	    correspLeafIds_.put(leafId1, leafId2);
	    return correspLeafIds_;
	} else {
	    Iterator childIter1 = n1_.getChildren();
	    Iterator childIter2 = n1_.getChildren();
	    return null;
	}
    }

    static class PatternVar extends LeafExpr {
	/** If non-null, only match nodes of this exact class. */
	private Class _class;
	PatternVar(Class class_) { super(Location.UNKNOWN); _class = class_; }
	PatternVar() { this(null); }
    }
}
